1. Field of the Invention
The present invention generally relates to the interconnection of nodes in data processing and communication systems and, more particularly, to a fast ring configuration mechanism that can be used to adaptively generate a consistent set of routing tables in each node of the network to facilitate passing data packets via a shortest path and/or a least congested path in the network.
2. Description of the Prior Art
There are many applications, including distributed systems, message passing clustering systems, loosely-coupled multi-processor systems, packet-switched networks, and the like which may be broadly described as a network of nodes interconnected by communication links. These applications tend to be very complex in practice. For the proper routing of data packets in the network, each node must have knowledge of its interconnection in the network relative to other nodes in the network. With this knowledge, a node can determine the shortest path to any other node in the network. In some cases, however, the shortest path may not be the fastest path to a destination node if that path is congested with other traffic. In such case, it is desirable to be able to determine at any node an alternative path which will result in the fastest transmission of a data packet to a destination node, given a current level of traffic in the network. Furthermore, when a node or nodes are added to or removed from the network, it is necessary to update the information at each node. A closely related problem involves fault tolerance of the network, as when a link between two nodes is broken, it is also necessary to provide the nodes with sufficient information necessary to choose an alternate path.
Various techniques are known for routing data packets over a multi-node data processing or communications network, and more specifically for routing each packet from an entry node to a destination node. It is common to represent the connectivity of nodes in a network by means of an undirected (fully duplex) graphs or a directional (simplex) graph. An undirected graph (or simply a graph) of N nodes is called "fully connected" if there is an edge (link) between every pair of nodes, or a directed edge (link) from every node to every other node, when the graph is directed (digraph).
FIG. 1 shows a fully connected digraph with N=4 nodes. Theoretically, a fully connected graph is attractive because it gives the best connectivity (since nodes are directly connected) with the minimum delay (since there is only one hop between nodes). However, it becomes less attractive when the design complexity and fault-tolerance are taken into consideration. To achieve the full connectivity for an undirected graph, a total of N(N-1)/2 connections is required. Obviously, for large N, the number of connections becomes unacceptably large, leading to a very complex interconnection system. When the edge joining a pair of nodes breaks, the communication between these two nodes is basically blocked (unless hopping through other nodes is allowed).